import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode:LCP 63. 弹珠游戏
 * <a href="https://leetcode.cn/problems/EXvqDp/">...</a>
 * User: DELL
 * Date: 2023-10-07
 * Time: 23:37
 */
public class Solution {
    private String[] plate;

    /**
     * 解题思路: (dfs)
     * 本题其实意图很明确,即大致两种思路,第一种就是遍历所有边界满足条件的点,
     * 模拟他们的运行路径,第二种就是根据洞来反向模拟,得到所有满足条件的点即可.
     * 一下解法主要是根据第一种思路.
     *
     * @param num
     * @param plate
     * @return
     */
    public int[][] ballGame(int num, String[] plate) {
        // 初始化全局变量
        this.plate = plate;
        List<int[]> list = new ArrayList<>();
        int n = plate.length;
        int m = plate[0].length();
        // 对方向有如下定义
        //    0
        // 3     1
        //    2
        // 遍历四个边界
        for (int j = 1; j < m - 1; j++) {
            // 上边界
            if (plate[0].charAt(j) == '.' && dfs(num, 0, j, 2)) {
                list.add(new int[]{0, j});
            }
            // 下边界
            if (plate[n - 1].charAt(j) == '.' && dfs(num, n - 1, j, 0)) {
                list.add(new int[]{n - 1, j});
            }
        }
        for (int i = 1; i < n - 1; i++) {
            // 左边界
            if (plate[i].charAt(0) == '.' && dfs(num, i, 0, 1)) {
                list.add(new int[]{i, 0});
            }
            // 有边界
            if (plate[i].charAt(m - 1) == '.' && dfs(num, i, m - 1, 3)) {
                list.add(new int[]{i, m - 1});
            }
        }
        // 整合数据
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private boolean dfs(int num, int i, int j, int direction) {
        // 判断是否入洞
        if (plate[i].charAt(j) == 'O') {
            return true;
        }
        // 判断是否还可以移动
        if (num == 0) {
            return false;
        }
        num--;
        char ch = plate[i].charAt(j);
        if (ch == 'E') {
            direction++;
        } else if (ch == 'W') {
            direction += 3;
        }
        direction %= 4;
        // 判断方向
        if ((i == 0 && direction == 0)
                || (i == plate.length - 1 && direction == 2)
                || (j == 0 && direction == 3)
                || (j == plate[0].length() - 1 && direction == 1)) {
            return false;
        }
        if (direction == 0) {
            i--;
        } else if (direction == 1) {
            j++;
        } else if (direction == 2) {
            i++;
        } else {
            j--;
        }
        return dfs(num, i, j, direction);
    }
}
